package interview.huawei.tjt.training.huisu;

import java.util.Scanner;

/**
 * 编写一个程序，通过填充空格来解决数独问题。
 *
 * 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
 *
 * 提示：
 * 给定的数独序列只包含数字 1-9 和字符 '.' 。
 * 你可以假设给定的数独只有唯一解。
 * 给定数独永远是 9x9 形式的。
 */
public class SolveSudoku {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[][] board = new char[9][9];
        for(int i=0;i<9;i++){
            char[] ch = in.nextLine().toCharArray();
            for(int j=0;j<9;j++){
                board[i][j] = ch[j];
            }
        }
        solveSudokuHelper(board);
        //输出二维矩阵
        for(int i=0;i<9;i++){
            for(int j=0;j<8;j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println(board[i][8]);//换行，每一行的最后一个数字
        }
    }

    private static boolean solveSudokuHelper (char[][] board) {
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (char k = '1'; k <= '9'; k ++) { // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)) {
                        board[i][j] = k;
                        if (solveSudokuHelper(board)) { // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private static boolean isValidSudoku (int row, int col, int val, char[][] board) {
        // 同行是否重复
        for (int i = 0; i < 9; i ++) {
            if (board[row][i] == val) {
                return false;
            }
        }

        // 同列是否重复
        for (int i = 0; i < 9; i ++) {
            if (board[i][col] == val) {
                return false;
            }
        }

        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i ++) {
            for (int j = startCol; i < startCol + 3; i ++) {
                if (board[i][j] == val){
                    return false;
                }
            }
        }

        return true;
    }

}
